USACO17JAN Cow Dance Show奶牛舞蹈

发表于 更新于 分类于

  • 题目链接：USACO17JAN Cow Dance Show奶牛舞蹈

  • 这是一道二分答案结合优先队列的题目，自我感觉对二分和贪心都有一定的帮助，毕竟是USACO的题目。。。

  • 大体说一下题意：你有n头奶牛，要进行一场表演，表演有一定的时间限制T，每头奶牛要表演a[i]个时间，你可以要求K头奶牛同时表演，求K的最小值。

  • 题目思路：我们不妨设二分的左右变量为奶牛同时表演的数目，同一个函数来判断当前mid是否符合题意，如果符合则缩小r，反之则扩大l，最终答案即为l。

  • 但是 _判断函数_ 怎么写？

如果按照模拟求解，显然会TLE，所以我们要进行相应的优化。

  • 判断函数优化思路

    让我们先来想一下怎样模拟——将a数组降序排列，然后每次枚举mid个，通过很复杂的处理来求出时间总和，最后再进行判断是否小于T。

那我们不妨这样想，既然要求最小时间，那我们何不用一个小根堆来存放时间，先把mid个时间放进去，再把剩余（n-mid）个的时间加到排好序的小根堆里，同时进行判断，如果不符题意，直接return 0，处理完这一步后，我们再取小根堆里前mid个数值进行判断，通过这两步判断，没有return的肯定符合题意。

  • 我们来思考一下，小根堆每次都要清零吗？

    我们每次check，都会往原时间上加内容，所以肯定比原时间要大，由此小根堆不需要清零，这也是用小根堆的好处，清零会浪费大量的时间，极有可能会TLE。

  • 那最后就是上代码了，有思路的同学就不要往下看了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define gc getchar()
#define Maxn 10010 //数据最大值 
using namespace std;
int ead() { //快读优化 
	int xx=0,ff=1; char cch;
	while(cch<'0'|| cch>'9') {
		if(cch=='-') ff=-ff; cch=gc;
	}
	while(cch>='0'&& cch<='9') {
		xx=xx*10+(cch-48); cch=gc;
	}
	return xx*ff;
}
int n,T,r,l; //n头牛，T个时间 
int a[Maxn];
priority_queue <int, vector <int>, greater <int> > q; //STL之小根堆 
namespace DY {
	bool check(int x) {  //check函数用来判断mid符不符合题意 
		for(int i=1; i<=x; i++)
			q.push(a[i]); //去mid个时间放进去 
		for(int i=x+1; i<=n; i++) { //枚举剩余的牛 
			int now=q.top(); q.pop();
			if(now>T) return 0; //超出时间限制，不符题意 
			now+=a[i]; //加上时间 
			q.push(now); //重新进栈 
		}
		for(int i=1; i<=x; i++) { //再判断前mid个时间是否合法 
			int now=q.top(); q.pop();
			if(now>T) return 0; //不合法 
		}
		return 1; //到最后肯定是符合题意了 
	}
	void main() {
		n=ead(); T=ead(); //输入 
		for(int i=1; i<=n; i++)
			a[i]=ead();
		l=1; r=n;
		while(l<=r) { //经典的二分模板 
			int mid=l+r>>1;
			if(check(mid)) r=mid-1;
			else l=mid+1;
		}
		printf("%d",l); //输出 
	}
};
int main() {
	DY::main();
	return 0;
}

祝大家（ _Of course including me_ ）RP++；